package algorithm.array;

import util.GsonUtil;

import java.util.*;

/**
 * leetcode : https://leetcode.com/problems/3sum/description/
 * Difficulty: Medium
 *
 * 参考解答:https://blog.csdn.net/EveryFriDay_ShuJk/article/details/80699012
 *
 * 给定 n个 整数的数组S，是否存在S中的元素a,b,c  使得 a+b+c=0.查找数组元素并且返回三元组
 * 注意：
 * 1) 三元组元素(a,b,c) 顺序必须是非降序 (a<=b<=c)
 * 2) 三元组去重
 *
 * 思路：
 * 1) 首先将数组排序.
 * 2) 定位第一个元素 i 然后使用两个指针 left=i+1 right=arr.length-1
 * 3) int temp =arr[i] + arr[left] + arr[right] = 0 则找到结果 然后left--;right++ 继续
 *      temp<0 说明结果小 left++
 *      temp>0 说明结果大 right--;
 * 4) 去除重复结果
 *      在找到结果时，需要循环判断指针接下来一个元素是否和当前重复，重复则继续移动指针直到不重复
 *
 * 注意：
 * 对数组排序以后，充分利用数组的有序性。可以排除那些重复处理过的数字
 *
 * @Author Antony
 * @Since 2018/6/27 15:34
 */
public class ThreeSum {


    public static void main(String[] args) {
        int[] arr = new int[]{-2,0,0,2,2};
        int[] arr_2 = new int[]{-1,0,1,2,-1,-4};
        System.out.println(GsonUtil.toJson(threeSum(arr)));
        System.out.println(GsonUtil.toJson(threeSum(arr_2)));

    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums == null){
            return result;
        }

        Arrays.sort(nums);
        int left,right,temp;
        for(int i=0; i<nums.length; i++){
            if(nums[i] > 0){    // 如果大于0 就不需要继续遍历了
                break;
            }
            // 跳过i重复的元素，还是利用的序列的有序性质
            if(i>0 && nums[i] == nums[i-1]){
                continue;
            }
            left = i+1;
            right = nums.length - 1;
            while(left<right){
                temp = nums[i] + nums[left] + nums[right];
                if(temp == 0){
                    List<Integer> list = Arrays.asList(nums[i],nums[left],nums[right]);
                    result.add(list);

                    // 循环校验。由于数组已经有序，所以这个操作可以跳过那些重复元素
                    // 从而可以对结果去重
                    while(left < right && nums[left]==list.get(1)) left++;
                    while(left < right && nums[right]==list.get(2)) right--;
                }else if(temp > 0){
                    right--;
                }else{
                    left++;
                }
            }
        }

        return result;
    }
}
